#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	int val;
}BTNode;

#include "Queue.h"

BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	if (NULL == newnode)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

//手搓一棵树
BTNode* CreateTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
	BTNode* n7 = BuyBTNode(7);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	n5->left = n7;

	return n1;
}

void PreOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

//int TreeSize(BTNode* root)
//{
//	static int size = 0;
//
//	if (NULL == root)
//	{
//		return 0;
//	}
//	else
//	{
//		++size;
//	}
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}



////static int size = 0;
//int size = 0;
//
//int TreeSize(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return 0;
//	}
//	else
//	{
//		++size;
//	}
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}


//void TreeSize(BTNode* root, int* psize)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//	else
//	{
//		++(*psize);
//	}
//
//	TreeSize(root->left, psize);
//	TreeSize(root->right, psize);
//}


int TreeSize(BTNode* root)
{
	return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeHeight(BTNode* root)
{
	if (NULL == root)
	{
		return 0;
	}

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);

	if (NULL == root)
	{
		return 0;
	}

	if (1 == k)
	{
		return 1;
	}

	//不等于空，且k > 1说明第k层的节点在子树里面，转换成子问题求解
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

//bool TreeFind(BTNode* root, int x)
//{
//	if (NULL == root)
//	{
//		return false;
//	}
//
//	if (root->val == x)
//	{
//		return true;
//	}
//
//	return TreeFind(root->left, x) || TreeFind(root->right, x);
//}


//BTNode* TreeFind(BTNode* root, int x)
//{
//	if (NULL == root)
//	{
//		return NULL;
//	}
//
//	if (root->val == x)
//	{
//		return root;
//	}
//
//	BTNode* ret1 = TreeFind(root->left, x);
//
//	if (ret1)
//	{
//		return ret1;
//	}
//	
//	BTNode* ret2 = TreeFind(root->right, x);
//
//	if (ret2)
//	{
//		return ret2;
//	}
//
//	return NULL;
//}


BTNode* TreeFind(BTNode* root, int x)
{
	if (NULL == root)
	{
		return NULL;
	}

	if (root->val == x)
	{
		return root;
	}

	BTNode* ret1 = TreeFind(root->left, x);

	if (ret1)
	{
		return ret1;
	}

	return TreeFind(root->right, x);
}



//bool isSameTree(struct TreeNode* p, struct TreeNode* q)
//{
//	//根
//	//左子树
//	//右子树
//
//	//都为空
//	if (p == NULL && q == NULL)
//	{
//		return true;
//	}
//
//	//其中一个为空
//	if (p == NULL || q == NULL)
//	{
//		return false;
//	}
//
//	if (p->val != q->val)
//	{
//		return false;
//	}
//
//	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}



//bool isUnivalTree(struct TreeNode* root)
//{
//	if (NULL == root)
//	{
//		return true;
//	}
//
//	if (root->left && root->left->val != root->val)
//	{
//		return false;
//	}
//
//	if (root->right && root->right->val != root->val)
//	{
//		return false;
//	}
//
//	return isUnivalTree(root->left) && isUnivalTree(root->right);
//}


//bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
//{
//	//根比较
//	//左子树和右子树比较
//	//右子树和左子树比较
//
//	//都为空
//	if (root1 == NULL && root2 == NULL)
//	{
//		return true;
//	}
//
//	//一个为空 另一个不为空
//	if (root1 == NULL || root2 == NULL)
//	{
//		return false;
//	}
//
//	if (root1->val != root2->val)
//	{
//		return false;
//	}
//
//	return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
//}
//
//bool isSymmetric(struct TreeNode* root)
//{
//	return _isSymmetric(root->left, root->right);
//}


//int TreeSize(struct TreeNode* root)
//{
//	return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//void preorder(struct TreeNode* root, int* a, int* pi)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//
//	a[(*pi)++] = root->val;
//	preorder(root->left, a, pi);
//	preorder(root->right, a, pi);
//}
//
//int* preorderTraversal(struct TreeNode* root, int* returnSize)
//{
//	*returnSize = TreeSize(root);
//	int* a = (int*)malloc(sizeof(int) * (*returnSize));
//	int i = 0;
//	preorder(root, a, &i);
//
//	return a;
//}


//bool isSameTree(struct TreeNode* p, struct TreeNode* q)
//{
//	//根
//	//左子树
//	//右子树
//
//	//都为空
//	if (p == NULL && q == NULL)
//	{
//		return true;
//	}
//
//	//其中一个为空
//	if (p == NULL || q == NULL)
//	{
//		return false;
//	}
//
//	if (p->val != q->val)
//	{
//		return false;
//	}
//
//	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}
//
////查找 + 树的比较
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
//{
//	if (NULL == root)
//	{
//		return false;
//	}
//
//	if (root->val == subRoot->val && isSameTree(root, subRoot))
//	{
//		return true;
//	}
//
//	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}

//void TreeDestroy(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//
//	TreeDestroy(root->left);
//	TreeDestroy(root->right);
//	free(root);
//}

//void TreeLevelOrder(BTNode* root)
//{
//	Queue q;
//	QueueInit(&q);
//
//	if (root)
//	{
//		QueuePush(&q, root);
//	}
//
//	while (!QueueEmpty(&q))
//	{
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//		printf("%d ", front->val);
//		
//		//带入下一层
//		if (front->left)
//		{
//			QueuePush(&q, front->left);
//		}
//
//		if (front->right)
//		{
//			QueuePush(&q, front->right);
//		}
//	}
//
//	printf("\n");
//	QueueDestroy(&q);
//}

void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			printf("%d ", front->val);

			//带入下一层
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			printf("N ");
		}
	}

	printf("\n");
	QueueDestroy(&q);
}

bool TreeIsComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
	{
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		//遇到空以后就跳出后续判断
		if (NULL == front)
		{
			break;
		}

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	//如果都是空，就是完全二叉树，存在非空就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

int main()
{
	BTNode* root = CreateTree();
	PreOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	//printf("%d\n", TreeSize(root));
	//size = 0;
	//printf("%d\n", TreeSize(root));
	//size = 0;
	//printf("%d\n", TreeSize(root));

	printf("TreeSize：%d\n", TreeSize(root));
	printf("TreeKLevel：%d\n", TreeKLevel(root, 4));

	printf("TreeFind：%p\n", TreeFind(root, 3));

	TreeLevelOrder(root);

	printf("TreeIsComplete:%d\n", TreeIsComplete(root));

	return 0;
}


//#include <stdio.h>
//#include <stdlib.h>
//
//typedef struct BinTreeNode
//{
//	struct BinTreeNode* left;
//	struct BinTreeNode* right;
//	char val;
//}BTNode;
//
//BTNode* CreateTree(char* a, int* pi)
//{
//	if ('#' == a[(*pi)])
//	{
//		(*pi)++;
//		return NULL;
//	}
//
//	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
//	root->val = a[(*pi)++];
//	root->left = CreateTree(a, pi);
//	root->right = CreateTree(a, pi);
//
//	return root;
//}
//
//void InOrder(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//
//	InOrder(root->left);
//	printf("%c ", root->val);
//	InOrder(root->right);
//}
//
//int main()
//{
//	char a[100];
//	scanf("%s", a);
//	int i = 0;
//	BTNode* root = CreateTree(a, &i);
//	InOrder(root);
//
//	return 0;
//}